package org.example.algorithm.binaryTree;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Test {

    /**
     * 力扣104:二叉树的最大深度。
     * 做法
     * 1.深度优先搜索。个人觉得是递归计数。（先、中、后序遍历）
     * 2.广度优先搜索。个人觉得就是一行一行的读取。队列+每行读取（层序遍历）
     */
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
//        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
//        单层队列
//        List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
//        int res = 0;
//        while (!queue.isEmpty()) {
//            tmp = new LinkedList<>();
//            for(TreeNode node : queue) {
//                if (node.left != null) tmp.add(node.left);
//                if (node.right != null) tmp.add(node.right);
//            }
//            queue = tmp;
//            res++;
//        }
//        return res;
        //单层队列
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            ans++;
        }
        return ans;
    }

    /**
     * 力扣100:相同的树
     * 思路和做法：
     * 1.深度优先搜索。个人觉得是递归计数。（先、中、后序遍历）
     * 2.广度优先搜索。个人觉得就是一行一行的读取。队列+每行读取（层序遍历）
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //深度优先搜索，先序遍历
//        if(p == null && q == null){
//            return true;
//        } else if (p == null || q == null) {
//            return false;
//        } else if (p.val != q.val) {
//            return false;
//        }
//        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        //广度优秀搜索。
        if(p == null && q == null){
            return true;
        } else if (p == null || q == null) {
            return false;
        }
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(p);
        queue2.offer(q);
        while(!queue1.isEmpty() && !queue2.isEmpty()){
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            if(node1.val != node2.val){
                return false;
            }
            TreeNode left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;
            if(left1 == null ^ left2 == null) return false;
            if(right1 == null ^ right2 == null) return false;
            if(left1 != null) queue1.offer(left1);
            if(right1 != null) queue1.offer(right1);
            if(left2 != null) queue2.offer(left2);
            if(right2 != null) queue2.offer(right2);
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }

    /**
     * 力扣226.翻转二叉树
     * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
     * 输入：root = [4,2,7,1,3,6,9]
     * 输出：[4,7,2,9,6,3,1]
     * 输入：root = [2,1,3]
     * 输出：[2,3,1]
     * 输入：root = []
     * 输出：[]
     *
     * 思路和做法：
     * 1.深度优先搜索。搜索到对应的字数交换对应的
     * 2.广度优先搜索。
     */
    public TreeNode invertTree(TreeNode root) {
        //临界条件判断
        if(root == null) return null;
        //1.深度优先搜索
//        TreeNode tempNode = root.left;
//        root.left = root.right;
//        root.right = tempNode;
//        invertTree(root.left);
//        invertTree(root.right);
//        return root;
        //2.广度优先搜索
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            TreeNode t = node.left;
            node.left = node.right;
            node.right = t;
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        return root;
    }

    /**
     * 力扣101.对称二叉树。
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     * root = [1,2,2,3,4,4,3]
     * 思路：
     * 做法1.深度优先搜索。递归左子树和右子树
     * 做法2.广度优先搜索
     */
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return dfs(root.left, root.right);
    }

    private boolean dfs(TreeNode left, TreeNode right) {
        if(left == null && right == null){
            return true;
        }
        if(left == null || right == null){
            return false;
        }
        if(left.val != right.val){
            return false;
        }
        return dfs(left.left, right.right) && dfs(left.right, right.left);
    }

    private boolean bfs(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while(!queue.isEmpty()){
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }

}
